import numpy as np

# ref from https://gitlab.com/-/snippets/1948157
# For some variants, look here https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

# Pure python
# def edit_distance_python2(a, b): # This version is not used, can be commented out or removed
#     # This version is commutative, so as an optimization we force |a|>=|b|
#     if len(a) < len(b):
#         return edit_distance_python(b, a)
#     if len(b) == 0:  # Can deal with empty sequences faster
#         return len(a)
#     # Only two rows are really needed: the one currently filled in, and the previous
#     distances = []
#     distances.append([i for i in range(len(b)+1)])
#     distances.append([0 for _ in range(len(b)+1)])
#     # We can prefill the first row:
#     costs = [0 for _ in range(3)]
#     for i, a_token in enumerate(a, start=1):
#         distances[1][0] += 1  # Deals with the first column.
#         for j, b_token in enumerate(b, start=1):
#             costs[0] = distances[1][j-1] + 1
#             costs[1] = distances[0][j] + 1
#             costs[2] = distances[0][j-1] + (0 if a_token == b_token else 1)
#             distances[1][j] = min(costs)
#         # Move to the next row:
#         distances[0][:] = distances[1][:]
#     return distances[1][len(b)]

# https://stackabuse.com/levenshtein-distance-and-text-similarity-in-python/
def edit_distance_python(seq1: str, seq2: str) -> int:
    # Ensure inputs are strings, handle None by converting to empty string
    s1 = seq1 if seq1 is not None else ""
    s2 = seq2 if seq2 is not None else ""

    size_x = len(s1) + 1
    size_y = len(s2) + 1
    matrix = np.zeros((size_x, size_y), dtype=int)

    for x in range(size_x):
        matrix[x, 0] = x
    for y in range(size_y):
        matrix[0, y] = y

    for x in range(1, size_x):
        for y in range(1, size_y):
            if s1[x-1] == s2[y-1]:
                matrix[x,y] = min(
                    matrix[x-1, y] + 1,    # Deletion from s1
                    matrix[x-1, y-1],      # Match/Substitution (cost 0 if match)
                    matrix[x, y-1] + 1     # Insertion into s1
                )
            else:
                matrix[x,y] = min(
                    matrix[x-1,y] + 1,     # Deletion
                    matrix[x-1,y-1] + 1,   # Substitution (cost 1)
                    matrix[x,y-1] + 1      # Insertion
                )
    return matrix[size_x - 1, size_y - 1] 